#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;

//递归方法超时
// class Solution {
// public:
//     int maxScore(vector<int>& cardPoints, int k) {
//         return func(cardPoints,k,1);
//     }
//     int func(vector<int> cardPointrs,int k,int i){
//         if(i==k){
//             return max(*cardPointrs.begin(),*cardPointrs.rbegin());
//         }
//         //选了左边的
//         int tempLeft = *cardPointrs.begin();
//         int maxLeft = func(vector<int>(cardPointrs.begin()+1,cardPointrs.end()),k,i+1);
//         //选了右边的
//         int tempRight = *cardPointrs.rbegin();
//         cardPointrs.pop_back();
//         int maxRight = func(vector<int>(cardPointrs.begin(),cardPointrs.end()-1),k,i+1);
//         return max(tempLeft+maxLeft,tempRight+maxRight);
//     }
// };

//使用滑动窗口解决
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        //假设初始时大小为k的窗口全在右边
        //我首先想计算前面N-k的值，求出前面最小值，剩余的就是最大值
        int minSum = 0;
        int i= 0;
        for(;i<cardPoints.size()-k;++i){
            minSum += cardPoints[i];
        }
        //滑动前面这个N-k的窗口
        int j = 0;
        int tempSum = minSum;
        for(;i<cardPoints.size();++i){
            tempSum = tempSum-cardPoints[j]+cardPoints[i];
            minSum  = min(tempSum,minSum);
            ++j;
        }
        return accumulate(cardPoints.begin(),cardPoints.end(),0)-minSum;


    }
};

int main(){
    Solution S;
    vector<int> nums = {1,2,3,4,5,6,1};
    cout<<S.maxScore(nums,3)<<endl;
}